Erratum to: “Communication Complexity and Intrinsic Universality in Cellular Automata” [Theor. Comput. Sci. 412 (1–2) (2011) 2–21]

AbstractProofs of Propositions 6 and 8 of the paper Communication Complexity and Intrinsic Universality in Cellular Automata are formally incorrect. This erratum proves weaker versions of Propositions 6 and 8 and a stronger version of Proposition 9 which are sufficient to get the main results of the paper (Corollary 2) for PREDICTION and INVASION problems. For problem CYCLE, we only prove a weaker version of Corollary 2, essentially replacing a condition of the form ‘f∈Ω(n)’ by ‘f∉o(n)’. All other statements of the paper are unaffected